package com.lw.leetcode.binary.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2528. 最大化城市的最小供电站数目
 * c
 * biany
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/8 16:47
 */
public class MaxPower {


    public static void main(String[] args) {
        MaxPower test = new MaxPower();

        // 5
//        int[] arr = {1, 2, 4, 5, 0};
//        int r = 1;
//        int k = 2;

        // 4
//        int[] arr = {4, 4, 4, 4};
//        int r = 0;
//        int k = 3;

        //
        int[] arr = Utils.getArr(10000, 1, 10000);
        int r = 1234;
        int k = 1000000000;

        long l = test.maxPower(arr, r, k);
        System.out.println(l);
    }


    public long maxPower(int[] stations, int r, int k) {
        int length = stations.length;
        long[] sums = new long[length + 1];
        for (int i = 0; i < length; i++) {
            sums[i + 1] = sums[i] + stations[i];
        }
        long min = Long.MAX_VALUE;
        for (int i = 1; i <= length; i++) {
            min = Math.min(min, sums[Math.min(i + r, length)] - sums[Math.max(i - r - 1, 0)]);
        }
        if (length <= (r << 1) + 1) {
            return min + k;
        }
        long st = min;
        long end = min + k;
        long[] items = new long[length + 2];
        long all = 0;
        while (st < end) {
            long m = st + ((end - st + 1) >> 1);
            int k1 = k;
            boolean flag = true;
            for (int i = 1; i <= length; i++) {
                all += items[i];
                long l = all + sums[Math.min(i + r, length)] - sums[Math.max(i - r - 1, 0)];

                if (l >= m) {
                    continue;
                }
                all += (m - l);
                k1 -= (m - l);
                if (k1 < 0) {
                    flag = false;
                    break;
                }
                int t = i + (r << 1) + 1;
                if (t < length + 2) {
                    items[t] = l - m;
                }
            }
            Arrays.fill(items, 0);
            all = 0;
            if (flag) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }
}
